package MyProject2;

public class MyArrayList {



    public static void add(int value,Node node){

        if (node == null){
            node = new Node(value,null);
            return;
        }

        Node p = node;
        while (p.next != null){
            p = p.next;
        }
        p.next = new Node(value,null);
    }

    public static Node merge(Node node1,Node node2){

        if (node1 == null){
            return node2;
        }
        if (node2 == null){
            return node1;
        }

        if (node1.value < node2.value){
            node1.next = merge(node1.next,node2);
            return node1;
        }else {

            node2.next = merge(node1,node2.next);
            return node2;
        }

    }

    public static Node sort(Node node){
        Node first = node;
        Node next = null;
        int temp = 0;
        while (first != null){
            next = first.next;
            while (next != null){
                if (first.value > next.value){
                    temp = first.value;
                    first.value = next.value;
                    next.value = temp;
                }
                next = next.next;
            }
            first = first.next;
        }
        return node;
    }

    private static void insert(Node node,Node insert){
        Node p = node;
        while (p != null){
            if (p.next.value > insert.value){
                Node temp = p.next;
                p.next = insert;
                insert.next = temp;
                break;
            }else {
                p = p.next;
            }
        }

    }




}

class Node{
    public int value;
    public Node next;

    public Node(int value, Node next) {
        this.value = value;
        this.next = next;
    }

    public Node() {
    }
}